from libc.stdint cimport uint64_t as u64, uint32_t as u32, uint8_t as u8, uint16_t as u16, int32_t as i32,\
    int16_t as i16, int8_t as i8, int64_t as i64, UINT64_MAX, UINT32_MAX, UINT16_MAX, INT64_MAX, INT64_MIN, UINT32_MAX, UINT8_MAX

from libc.string cimport memcpy, memcmp, memset, strlen, memmove
from libc.stdlib cimport malloc, free

include "num.pyx"
cdef class TestUintSetRange:
    cdef readonly :
        UintSet s
        u64 start, end, cur, step, block
    def __init__(self, s:UintSet, start:int, end:int, step:int, block:int):
        self.s, self.start,self.end, self.block=s, start, end, block
        self.step = step
        self.cur=self.start
    def __iter__(self):
        return self
    def next_add(self):
        cdef u64 i, cur=self.cur, end=cur+self.block
        cdef UintSet s = self.s
        end=end if end<self.end else self.end+1
        if cur<end:
            while(cur<end):
                s=s.add(cur)#
                assert s.contains(cur)
                cur += self.step
            self.s=s
            self.cur=end
            return s
        else:
            raise StopIteration
    def next_remove(self):
        cdef u64 i, cur = self.cur, end = cur + self.block
        cdef UintSet s = self.s
        end = end if end < self.end else self.end + 1
        if cur < end:
            while (cur < end):
                s = s.remove(cur)  #
                assert not s.contains(cur)
                cur += self.step
            self.s = s
            self.cur = end
            return s
        else:
            raise StopIteration
cdef class TestUintSetRangeAdd(TestUintSetRange):
    def __next__(self):
        return self.next_add()

cdef class TestUintSetRangeRemove(TestUintSetRange):
    def __next__(self):
        return self.next_remove()

#----------------------------------------------------------------------------------------------------------------------
ctypedef fused uInt1:
    u64
    u32
    u16

cdef u8* malloc_raise(u64 size):
    cdef u8* p=<u8*>malloc(size)
    if p != NULL:
        return p
    else:
        raise MemoryError(f'need {(size) / (ONE << 20)}MB memory')
cdef new_obj(type t, u64 size):
    try:
        return t()
    except MemoryError as e:
        raise MemoryError(f'need {(size)/(ONE<<20)}MB memory') from e

cdef volatile void my_memset0(volatile void* data,u64 nbytes):
    cdef u64 shang8=nbytes>>3, mod=nbytes&7, i
    cdef volatile u64* ptr8=<volatile u64*>data
    for i in range(shang8):
        ptr8[i]=0
    cdef volatile u8* ptr=<volatile u8*>(ptr8+shang8)
    for i in range(mod):
        ptr[i]=0

#-----------------------------------------------------------------------------------------------------------------------

cpdef UintSet copy_to_new_set_n(UintSet set0, UintSet set1, u64 cur):
    cdef u64 i=0, v, count=0
    while(count<cur):
        #print(f'count={count}, cur={cur}, i={i}, set0:{type(set0)}, set1:{type(set1)} debug copy to new set')
        v=set0._next(&i)
        #print(f'v={v}, i={i}, s1cur:{set1._cur()}, debug copy to new set')
        set1._append(v)
        #print(f'v={v}, i={i}, s1cur:{set1._cur()}, debug copy to new set append after')
        count += 1
        i+=1
#---------------------------------------------next-array-set------------------------------------------------------------
cdef u64 next_u8_arrayset(u8* arrayset, u64* iptr):
    cdef u64 i=iptr[0]
    return arrayset[i]

cdef u64 next_u16_arrayset(u16* arrayset, u64* iptr):
    cdef u64 i=iptr[0]
    return arrayset[i]

cdef u64 next_u32_arrayset(u32* arrayset, u64* iptr):
    cdef u64 i=iptr[0]
    return arrayset[i]

cdef u64 next_u24_arrayset(u16* low, u8* high, u64* iptr):
    cdef u64 i=iptr[0]
    return low[i]+(high[i]<<32)

cdef u64 next_u40_arrayset(u32* low, u8* high, u64* iptr):
    cdef u64 i=iptr[0]
    return low[i]+(high[i]<<32)

cdef u64 next_u48_arrayset(u32* low, u16* high, u64* iptr):
    cdef u64 i=iptr[0]
    return low[i]+(high[i]<<32)

cdef u64 next_u64_arrayset(u64* arrayset, u64* iptr):
    cdef u64 i=iptr[0]
    return arrayset[i]
#---------------------------------------------next-hashset--------------------------------------------------------------
cdef u64 next_u8_hashset(u8* hashset, u64* iptr):
    cdef u64 i=iptr[0]
    while(hashset[i] == 0):
        i+=1
    iptr[0]=i
    return hashset[i]

cdef u64 next_u16_hashset(u16* hashset, u64* iptr):
    cdef u64 i = iptr[0]
    while(hashset[i] == 0):
        i+=1
    iptr[0]=i
    return hashset[i]

cdef u64 next_u32_hashset(u32* hashset, u64* iptr):
    cdef u64 i = iptr[0]
    while (hashset[i] == 0):
        i += 1
    iptr[0] = i
    return hashset[i]

cdef u64 next_u24_hashset(u16* low, u8* high, u64* iptr):
    cdef u64 i = iptr[0],highv=high[i]
    while (low[i] == 0 and highv==0):
        i += 1
    iptr[0] = i
    return low[i]+(highv<<16)

cdef u64 next_u40_hashset(u32* low, u8* high, u64* iptr):
    cdef u64 i = iptr[0],highv=high[i]
    while (low[i] == 0 and highv==0):
        i += 1
    iptr[0] = i
    return low[i]+(highv<<32)

cdef u64 next_u48_hashset(u32* low, u16* high, u64* iptr):
    cdef u64 i = iptr[0], highv=high[i]
    while (low[i] == 0 and highv == 0):
        i += 1
    iptr[0] = i
    return low[i] + (highv << 32)

cdef u64 next_u64_hashset(u64* hashset, u64* iptr):
    cdef u64 i = iptr[0]
    while (hashset[i] == 0):
        i += 1
    iptr[0] = i
    return hashset[i]

cdef u64 next_bitset_1(u64 v, u64 i, u64 start_bit, u64* iptr):
    cdef u64 ibit, flag=ONE<<start_bit,vv
    for ibit in range(start_bit,64):
        ##print(f'flag={flag}, v={str_bitstring(v)}, ibit={ibit}, i={i}, debug next bitset_1')
        if v&flag:
            vv=(i<<6) + ibit
            iptr[0] = vv
            return vv
        else: flag<<=1
    return 0

cdef u64 next_bitset(u64* data, u64 * i):
    cdef u64 ii = i[0], iii = ii >> 6, jj = ii & 63, flag = ONE << jj, v = data[iii], jjj, j
    j=next_bitset_1(v, iii, jj, i)
    if j!=0:
        return j
    while(1):
        iii+=1
        v=data[iii]
        ##print(f'iii={iii}, v={str_bitstring(v)}, j={j}, debug next bitset')
        if v==0:continue
        else:
            j=next_bitset_1(v, iii, 0, i)
            ##print(f'j={j}, iii={iii}, v={str_bitstring(v)}, debug next bitset')
            assert j!=0
            return j

#-----------------------------------------------bisect-in---------------------------------------------------------------
cdef u64 bisect_u8_in(u8* arr, u64 val, uint count, uint* eq):
    cdef u64 low=0, high=count, mi
    while(low<high):
        mi = (low+high)>>1
        if arr[mi]<val:
            low = mi + 1
        elif arr[mi]>val:
            high = mi
        else:
            eq[0]=1
            return mi
    eq[0]=0
    return low

cdef u64 bisect_u16_in(u16* arr, u64 val, uint count, uint* eq):
    cdef u64 low=0, high=count, mi
    while(low<high):
        mi = (low+high)>>1
        if arr[mi]<val:
            low = mi + 1
        elif arr[mi]>val:
            high = mi
        else:
            eq[0]=1
            return mi
    eq[0]=0
    return low

cdef u64 bisect_u32_in(u32* arr, u64 val, uint count, uint* eq):
    cdef u64 low=0, high=count, mi
    while(low<high):
        mi = (low+high)>>1
        if arr[mi]<val:
            low = mi + 1
        elif arr[mi]>val:
            high = mi
        else:
            eq[0]=1
            return mi
    eq[0]=0
    return low

cdef u64 bisect_u24_in(u16* lows, u8* highs, u64 val, uint count, uint* eq):
    cdef u64 low=0, high=count, mi, mid, highv
    while(low<high):
        mi = (low+high)>>1
        highv = highs[mi]
        mid = (highv<<16) + lows[mi]
        if mid<val:
            low = mi + 1
        elif mid>val:
            high = mi
        else:
            eq[0]=1
            return mi
    eq[0]=0
    return low

cdef u64 bisect_u40_in(u32* lows, u8* highs, u64 val, uint count, uint* eq):
    cdef u64 low=0, high=count, mi, mid, highv
    while(low<high):
        mi = (low+high)>>1
        highv = highs[mi]
        mid = (highv<<32) + lows[mi]
        if mid<val:
            low = mi + 1
        elif mid>val:
            high = mi
        else:
            eq[0]=1
            return mi
    eq[0]=0
    return low

cdef u64 bisect_u48_in(u32* lows, u16* highs, u64 val, uint count, uint* eq):
    cdef u64 low=0, high=count, mi, mid, highv
    while(low<high):
        mi = (low+high)>>1
        highv = highs[mi]
        mid = (highv<<32) + lows[mi]
        if mid<val:
            low = mi + 1
        elif mid>val:
            high = mi
        else:
            eq[0]=1
            return mi
    eq[0]=0
    return low

cdef u64 bisect_u64_in(u64* arr, u64 val, uint count, uint* eq):
    cdef u64 low=0, high=count, mi
    while(low<high):
        mi = (low+high)>>1
        if arr[mi]<val:
            low = mi + 1
        elif arr[mi]>val:
            high = mi
        else:
            eq[0]=1
            return mi
    eq[0]=0
    return low

#-----------------------------------------------bisect-insert-----------------------------------------------------------
cdef u64 bisect_insert_u8(u8* arr, u64 val, u64 count):
    cdef uint eq, i=bisect_u8_in(arr, val, count, &eq), ii, j
    ##print(i, eq, count, 'debug bisect insert u8')
    cdef u8 temp0, temp1
    if eq:
        return UINT64_MAX
    else:
        temp0=val
        for ii in range(i,count):
            temp1 = arr[ii]
            arr[ii]=temp0
            temp0 = temp1
        arr[count]=temp0
        #print(ii, i, temp0, 'debug bisect insert u8')
        return i
    
cdef u64 bisect_insert_u16(u16* arr, u64 val, u64 count):
    cdef uint eq, i=bisect_u16_in(arr, val, count, &eq), ii, j
    cdef u16 temp0, temp1
    if eq:
        return UINT64_MAX
    else:
        temp0=val
        for ii in range(i,count):
            temp1 = arr[ii]
            arr[ii]=temp0
            temp0 = temp1
        arr[count]=temp0
        return i
    
cdef u64 bisect_insert_u32(u32* arr, u64 val, u64 count):
    cdef uint eq, i=bisect_u32_in(arr, val, count, &eq), ii, j
    cdef u32 temp0, temp1
    if eq:
        return UINT64_MAX
    else:
        temp0=val
        for ii in range(i,count):
            temp1 = arr[ii]
            arr[ii]=temp0
            temp0 = temp1
        arr[count]=temp0
        return i


cdef u64 bisect_insert_u24(u16* low, u8* high, u64 val, u64 count):
    cdef uint eq, i=bisect_u24_in(low, high, val, count, &eq), ii, j
    cdef u64 temp0low, temp1low, temp0high, temp1high
    if eq:
        return UINT64_MAX
    else:
        temp0high=val>>16
        temp0low=val&UINT16_MAX
        for ii in range(i,count):
            temp1low = low[ii]
            temp1high = high[ii]
            low[ii]=temp0low
            high[ii]=temp0high
            temp0low = temp1low
            temp0high = temp1high
        low[count]=temp0low
        high[count]=temp0high
        return i

cdef u64 bisect_insert_u40(u32* low, u8* high, u64 val, u64 count):
    cdef uint eq, i=bisect_u40_in(low, high, val, count, &eq), ii, j
    cdef u64 temp0low, temp1low, temp0high, temp1high
    if eq:
        return UINT64_MAX
    else:
        temp0high=val>>32
        temp0low=val&UINT32_MAX
        for ii in range(i,count):
            temp1low = low[ii]
            temp1high = high[ii]
            low[ii]=temp0low
            high[ii]=temp0high
            temp0low = temp1low
            temp0high = temp1high
        low[count]=temp0low
        high[count]=temp0high
        return i

cdef u64 bisect_insert_u48(u32* low, u16* high, u64 val, u64 count):
    cdef uint eq, i=bisect_u48_in(low, high, val, count, &eq), ii, j
    cdef u64 temp0low, temp1low, temp0high, temp1high
    if eq:
        return UINT64_MAX
    else:
        temp0high=val>>32
        temp0low=val&UINT32_MAX
        for ii in range(i,count):
            temp1low = low[ii]
            temp1high = high[ii]
            low[ii]=temp0low
            high[ii]=temp0high
            temp0low = temp1low
            temp0high = temp1high
        low[count]=temp0low
        high[count]=temp0high
        return i
    
cdef u64 bisect_insert_u64(u64* arr, u64 val, u64 count):
    cdef uint eq, i=bisect_u64_in(arr, val, count, &eq), ii, j
    cdef u64 temp0, temp1
    if eq:
        return UINT64_MAX
    else:
        temp0=val
        for ii in range(i,count):
            temp1 = arr[ii]
            arr[ii]=temp0
            temp0 = temp1
        arr[count]=temp0
        return i
#-----------------------------------------------------------------------------------------------------------------------
cdef u64 bisect_remove_u8(u8* arr, u64 val, u64 count, ):
    cdef uint eq, i=bisect_u8_in(arr, val, count, &eq), ii, j
    cdef uInt temp0, temp1
    if eq:
        for ii in range(i,count-1):
            arr[ii]=arr[ii+1]
        return i
    else:
        return UINT64_MAX

cdef u64 bisect_remove_u16(u16* arr, u64 val, u64 count, ):
    cdef uint eq, i=bisect_u16_in(arr, val, count, &eq), ii, j
    cdef uInt temp0, temp1
    if eq:
        for ii in range(i,count-1):
            arr[ii]=arr[ii+1]
        return i
    else:
        return UINT64_MAX
    
cdef u64 bisect_remove_u32(u32* arr, u64 val, u64 count, ):
    cdef uint eq, i=bisect_u32_in(arr, val, count, &eq), ii, j
    cdef uInt temp0, temp1
    if eq:
        for ii in range(i,count-1):
            arr[ii]=arr[ii+1]
        return i
    else:
        return UINT64_MAX
    
cdef u64 bisect_remove_u64(u64* arr, u64 val, u64 count, ):
    cdef uint eq, i=bisect_u64_in(arr, val, count, &eq), ii, j
    cdef uInt temp0, temp1
    if eq:
        for ii in range(i,count-1):
            arr[ii]=arr[ii+1]
        return i
    else:
        return UINT64_MAX

cdef u64 bisect_remove_u24(u16* low, u8* high, u64 val, u64 count):
    cdef uint eq, i=bisect_u24_in(low, high, val, count, &eq), ii, j
    if eq:
        for ii in range(i,count-1):
            low[ii]=low[ii+1]
            high[ii]=high[ii+1]
        return i
    else:
        return UINT64_MAX

cdef u64 bisect_remove_u40(u32* low, u8* high, u64 val, u64 count):
    cdef uint eq, i=bisect_u40_in(low, high, val, count, &eq), ii, j
    if eq:
        for ii in range(i,count-1):
            low[ii]=low[ii+1]
            high[ii]=high[ii+1]
        return i
    else:
        return UINT64_MAX

cdef u64 bisect_remove_u48(u32* low, u16* high, u64 val, u64 count):
    cdef uint eq, i=bisect_u48_in(low, high, val, count, &eq), ii, j
    if eq:
        for ii in range(i,count-1):
            low[ii]=low[ii+1]
            high[ii]=high[ii+1]
        return i
    else:
        return UINT64_MAX
#---------------------------------------hash-search-in------------------------------------------------------------------
cdef uint PERTURB_SHIFT=5

cdef u64 u8_hash_search_in(u8* hashset, u64 mask, u64 val):
    cdef u64 perturb = val
    cdef u64 i=val&mask, j
    while(1):
        if hashset[i]==0:
            return UINT64_MAX
        elif hashset[i]!=val:
            perturb >>= PERTURB_SHIFT
            i = mask & (i * 5 + perturb + 1)
        else:
            return i
    raise AssertionError('Unreachable')

cdef u64 u16_hash_search_in(u16* hashset, u64 mask, u64 val):
    cdef u64 perturb = val
    cdef u64 i=val&mask, j
    while(1):
        if hashset[i]==0:
            return UINT64_MAX
        elif hashset[i]!=val:
            perturb >>= PERTURB_SHIFT
            i = mask & (i * 5 + perturb + 1)
        else:
            return i
    raise AssertionError('Unreachable')

cdef u64 u32_hash_search_in(u32* hashset, u64 mask, u64 val):
    cdef u64 perturb = val
    cdef u64 i=val&mask, j
    while(1):
        if hashset[i]==0:
            return UINT64_MAX
        elif hashset[i]!=val:
            perturb >>= PERTURB_SHIFT
            i = mask & (i * 5 + perturb + 1)
        else:
            return i
    raise AssertionError('Unreachable')


cdef u64 u24_hash_search_in(u16* low, u8* high, u64 mask, u64 val):
    cdef u64 perturb = val, v
    cdef u64 i=val&mask, j
    while(1):
        v = ((<u64>high[i])<<16) + low[i]
        if v==0:
            return UINT64_MAX
        elif v!=val:
            perturb >>= PERTURB_SHIFT
            i = mask & (i * 5 + perturb + 1)
        else:
            return i
    raise AssertionError('Unreachable')

cdef u64 u40_hash_search_in(u32* low, u8* high, u64 mask, u64 val):
    cdef u64 perturb = val, v
    cdef u64 i=val&mask, j
    while(1):
        v = ((<u64>high[i])<<32) + low[i]
        if v==0:
            return UINT64_MAX
        elif v!=val:
            perturb >>= PERTURB_SHIFT
            i = mask & (i * 5 + perturb + 1)
        else:
            return i
    raise AssertionError('Unreachable')

cdef u64 u48_hash_search_in(u32* low, u16* high, u64 mask, u64 val):
    cdef u64 perturb = val, v
    cdef u64 i=val&mask, j
    while(1):
        v = (<u64>high[i])<<32 + low[i]
        if v==0:
            return UINT64_MAX
        elif v!=val:
            perturb >>= PERTURB_SHIFT
            i = mask & (i * 5 + perturb + 1)
        else:
            return i
    raise AssertionError('Unreachable')

cdef u64 u64_hash_search_in(u64* hashset, u64 mask, u64 val):
    cdef u64 perturb = val
    cdef u64 i=val&mask, j
    while(1):
        if hashset[i]==0:
            return UINT64_MAX
        elif hashset[i]!=val:
            perturb >>= PERTURB_SHIFT
            i = mask & (i * 5 + perturb + 1)
        else:
            return i
    raise AssertionError('Unreachable')

#----------------------------------------------hash-insert--------------------------------------------------------------
cdef u64 u8_hash_insert(u8* hashset, u64 mask, u64 val):
    cdef u64 perturb = val
    cdef u64 i=val&mask, j
    while(1):
        if hashset[i]==0:
            hashset[i]=val
            return i
        elif hashset[i]!=val:
            perturb >>= PERTURB_SHIFT
            i = mask & (i * 5 + perturb + 1)
        else:
            return UINT64_MAX
        
cdef u64 u16_hash_insert(u16* hashset, u64 mask, u64 val):
    cdef u64 perturb = val
    cdef u64 i=val&mask, j
    while(1):
        if hashset[i]==0:
            hashset[i]=val
            return i
        elif hashset[i]!=val:
            perturb >>= PERTURB_SHIFT
            i = mask & (i * 5 + perturb + 1)
            #print(f'hashset[{i}]={hashset[i]}, pertub={perturb}, mask={mask}, val={val},debug u16 hash insert')
        else:
            return UINT64_MAX
        
cdef u64 u32_hash_insert(u32* hashset, u64 mask, u64 val):
    cdef u64 perturb = val
    cdef u64 i=val&mask, j
    while(1):
        if hashset[i]==0:
            hashset[i]=val
            return i
        elif hashset[i]!=val:
            perturb >>= PERTURB_SHIFT
            i = mask & (i * 5 + perturb + 1)
        else:
            return UINT64_MAX


cdef u64 u24_hash_insert(u16* low, u8* high, u64 mask, u64 val):
    cdef u64 perturb = val, v
    cdef u64 i=val&mask, j
    while(1):
        v = ((<u64>high[i])<<16) + low[i]
        if v==0:
            low[i]=val&UINT24_MAX
            high[i]=val>>16
            return i
        elif v!=val:
            perturb >>= PERTURB_SHIFT
            i = mask & (i * 5 + perturb + 1)
        else:
            return UINT64_MAX
    raise AssertionError('Unreachable')

cdef u64 u40_hash_insert(u32* low, u8* high, u64 mask, u64 val):
    cdef u64 perturb = val, v
    cdef u64 i=val&mask, j
    while(1):
        v = ((<u64>high[i])<<32) + low[i]
        if v==0:
            low[i]=val&UINT32_MAX
            high[i]=val>>32
            return i
        elif v!=val:
            perturb >>= PERTURB_SHIFT
            i = mask & (i * 5 + perturb + 1)
        else:
            return UINT64_MAX
    raise AssertionError('Unreachable')

cdef u64 u48_hash_insert(u32* low, u16* high, u64 mask, u64 val):
    cdef u64 perturb = val, v
    cdef u64 i=val&mask, j
    while(1):
        v = ((<u64>high[i])<<32) + low[i]
        if v==0:
            low[i]=val&UINT32_MAX
            high[i]=val>>32
            return i
        elif v!=val:
            perturb >>= PERTURB_SHIFT
            i = mask & (i * 5 + perturb + 1)
        else:
            return UINT64_MAX
    raise AssertionError('Unreachable')

cdef u64 u64_hash_insert(u64* hashset, u64 mask, u64 val):
    cdef u64 perturb = val
    cdef u64 i=val&mask, j
    while(1):
        if hashset[i]==0:
            hashset[i]=val
            return i
        elif hashset[i]!=val:
            perturb >>= PERTURB_SHIFT
            i = mask & (i * 5 + perturb + 1)
        else:
            return UINT64_MAX

#----------------------------------------------hash-remove--------------------------------------------------------------
cdef u64 u8_remove_hash(u8* hashset, u64 mask, u64 val):
    cdef u64 perturb = val
    cdef u64 i=u8_hash_search_in(hashset, mask, val)
    if i!=UINT64_MAX:
        hashset[i]=0
    return i

cdef u64 u16_remove_hash(u16* hashset, u64 mask, u64 val):
    cdef u64 perturb = val
    cdef u64 i=u16_hash_search_in(hashset, mask, val)
    if i!=UINT64_MAX:
        hashset[i]=0
    return i

cdef u64 u32_remove_hash(u32* hashset, u64 mask, u64 val):
    cdef u64 perturb = val
    cdef u64 i=u32_hash_search_in(hashset, mask, val)
    print(f'i={i}, val={val}, debug u32 remove hash')
    if i!=UINT64_MAX:
        print(f'hashset[{i}]={hashset[i]} set 0, debug u32 remove hash')
        hashset[i]=0
    return i

cdef u64 u64_remove_hash(u64* hashset, u64 mask, u64 val):
    cdef u64 perturb = val
    cdef u64 i=u64_hash_search_in(hashset, mask, val)
    if i!=UINT64_MAX:
        hashset[i]=0
    return i


cdef u64 u24_remove_hash(u16* low, u8* high, u64 mask, u64 val):
    cdef u64 perturb = val&UINT16_MAX
    cdef u64 i=u24_hash_search_in(low, high, mask, val)
    if i!=UINT64_MAX:
        high[i]=0
        low[i]=0
    return i

cdef u64 u40_remove_hash(u32* low, u8* high, u64 mask, u64 val):
    cdef u64 perturb = val&UINT32_MAX
    cdef u64 i=u40_hash_search_in(low, high, mask, val)
    if i!=UINT64_MAX:
        high[i] = 0
        low[i] = 0
    return i

cdef u64 u48_remove_hash(u32* low, u16* high, u64 mask, u64 val):
    cdef u64 perturb = val&UINT32_MAX
    cdef u64 i=u48_hash_search_in(low, high, mask, val)
    if i!=UINT64_MAX:
        high[i] = 0
        low[i] = 0
    return i

#-----------------------------------ge_choose---------------------------------------------------------------------------
cpdef UintSet ge16_val_choose_uint_set(u64 val, u64 cur):
    if val <= UINT16_MAX:
        return size_choose_u16set(cur)
    else:
        return ge24_val_choose_uint_set(val, cur)

cpdef UintSet ge24_val_choose_uint_set(u64 val, u64 cur):
    if val <= UINT24_MAX:
        return size_choose_u24set(cur)
    else:
        return ge32_val_choose_uint_set(val, cur)

cpdef UintSet ge32_val_choose_uint_set(u64 val, u64 cur):
    if val <= UINT32_MAX:
        return size_choose_u32set(cur)
    else:
        return ge40_val_choose_uint_set(val, cur)

cpdef UintSet ge40_val_choose_uint_set(u64 val, u64 cur):
    if val <= UINT40_MAX:
        return size_choose_u40set(cur)
    else:
        return size_choose_u48set(cur)

cpdef UintSet ge48_val_choose_uint_set(u64 val, u64 cur):
    if val <= UINT48_MAX:
        s=size_choose_u48set(cur)
    else:
        s = size_choose_u64set(cur)

#--------------------------------------------set-add--------------------------------------------------------------------
cpdef UintSet u8_set_add(UintSet self, u64 cur, u64 maxsize, u64 val):
    cdef UintSet s
    if val <= UINT8_MAX:
        if cur<maxsize:
            self._insert(val)
            return self
        else:
            s=size_choose_u8set(cur+1)
    else:
        s=ge16_val_choose_uint_set(val, cur+1)
        #
    #print(type(s), 'debug add u8')
    copy_to_new_set_n(self, s, cur)
    s._insert(val)
    return s

cpdef UintSet u16_set_add(UintSet self, u64 cur, u64 maxsize, u64 val):
    cdef UintSet s
    if val <= UINT16_MAX:
        if cur<maxsize:
            self._insert(val)
            return self
        else:
            s=size_choose_u16set(cur+1)
    else:
        s=ge32_val_choose_uint_set(val, cur+1)
    #
    copy_to_new_set_n(self, s, cur)
    s._insert(val)
    return s

cpdef UintSet u32_set_add(UintSet self, u64 cur, u64 maxsize, u64 val):
    cdef UintSet s
    if val <= UINT32_MAX:
        if cur<maxsize:
            self._insert(val)
            return self
        else:
            s=size_choose_u32set(cur+1)
    else:
        s=ge40_val_choose_uint_set(val, cur+1)
    #
    copy_to_new_set_n(self, s, cur)
    s._insert(val)
    return s


cpdef UintSet u24_set_add(UintSet self, u64 cur, u64 maxsize, u64 val):
    cdef UintSet s
    if val <= UINT24_MAX:
        if cur<maxsize:
            self._insert(val)
            return self
        else:
            s=size_choose_u24set(cur+1)
    else:
        s=ge32_val_choose_uint_set(val, cur+1)
    #
    copy_to_new_set_n(self, s, cur)
    s._insert(val)
    return s

cpdef UintSet u40_set_add(UintSet self, u64 cur, u64 maxsize, u64 val):
    cdef UintSet s
    if val <= UINT40_MAX:
        if cur<maxsize:
            self._insert(val)
            return self
        else:
            s=size_choose_u40set(cur+1)
    else:
        s=ge48_val_choose_uint_set(val, cur+1)
    #
    copy_to_new_set_n(self, s, cur)
    s._insert(val)
    return s

cpdef UintSet u48_set_add(UintSet self, u64 cur, u64 maxsize, u64 val):
    cdef UintSet s
    if val <= UINT48_MAX:
        if cur<maxsize:
            self._insert(val)
            return self
        else:
            s=size_choose_u48set(cur+1)
    else:
        s=size_choose_u64set(cur+1)
    #
    copy_to_new_set_n(self, s, cur)
    s._insert(val)
    return s

cpdef UintSet u64_set_add(UintSet self, u64 cur, u64 maxsize, u64 val):
    cdef UintSet s
    if cur<maxsize:
        self._insert(val)
        return self
    else:
        s=size_choose_u64set(cur)
    #
    copy_to_new_set_n(self, s, cur)
    s._insert(val)
    return s
#----------------------------------------------bitset-add---------------------------------------------------------------
cpdef UintSet u8bitset_add(UintSet self, u64 cur, u64 val):
    cdef UintSet s
    if val <= UINT8_MAX:
        self._insert(val)
        return self
    else:
        s=ge16_val_choose_uint_set(val, cur+1)
        copy_to_new_set_n(self, s, cur)
        s._insert(val)
        return s

cpdef UintSet u16bitset_add(UintSet self, u64 cur, u64 val):
    cdef UintSet s
    if val <= UINT16_MAX:
        self._insert(val)
        return self
    else:
        s=ge32_val_choose_uint_set(val, cur)
        copy_to_new_set_n(self, s, cur)
        s._insert(val)
        return s

cpdef UintSet u32bitset_add(UintSet self, u64 cur, u64 val):
    cdef UintSet s
    if val <= UINT32_MAX:
        self._insert(val)
        return self
    else:
        print(f'val={val}, diff={val-UINT32_MAX}, debug u32bitset level up')
        s=ge40_val_choose_uint_set(val, cur)
        copy_to_new_set_n(self, s, cur)
        s._insert(val)
        return s

cpdef UintSet u40bitset_add(UintSet self, u64 cur, u64 val):
    cdef UintSet s
    if val <= UINT40_MAX:
        self._insert(val)
        return self
    else:
        s=ge48_val_choose_uint_set(val, cur)
        copy_to_new_set_n(self, s, cur)
        s._insert(val)
        return s
    
cpdef UintSet u48bitset_add(UintSet self, u64 cur, u64 val):
    cdef UintSet s
    if val <= UINT48_MAX:
        self._insert(val)
        return self
    else:
        s=size_choose_u64set(cur)
        copy_to_new_set_n(self, s, cur)
        s._insert(val)
        return s

cpdef UintSet u64bitset_add(UintSet self, u64 cur, u64 val):
    cdef UintSet s
    self._insert(val)
    return self

#-----------------------------------------set-remove--------------------------------------------------------------------
cpdef UintSet u8_set_remove(UintSet self, u64 cur, u64 minsize, u64 val ):
    cdef UintSet s
    #print(f'cur={cur}, minsize={minsize}, val={val}, debug u8_set_remove')
    if val <= UINT8_MAX:
        #
        if cur < minsize:
            s=size_choose_u8set(cur)
            #print(f's:{type(s)}, debug u8_set_remove')
            copy_to_new_set_n(self, s, cur)
            s._remove(val)
            return s
        else:
            self._remove(val)
            return self
    else:
        return self
    
cpdef UintSet u16_set_remove(UintSet self, u64 cur, u64 minsize, u64 val, ):
    cdef UintSet s
    #print(f'self:{type(self)},cur={cur}, minsize={minsize}, val={val}, debug u16_set_remove')
    if val <= UINT16_MAX:
        #
        if cur < minsize:
            s=size_choose_u16set(cur)
            #print(f's:{type(s)}, debug u16_set_remove')
            copy_to_new_set_n(self, s, cur)
            s._remove(val)
            return s
        else:
            self._remove(val)
            return self
    else:
        return self
    
cpdef UintSet u32_set_remove(UintSet self, u64 cur, u64 minsize, u64 val):
    cdef UintSet s
    if val <= UINT40_MAX:
        #
        if cur < minsize:
            s=size_choose_u32set(cur)
            copy_to_new_set_n(self, s, cur)
            s._remove(val)
            return s
        else:
            self._remove(val)
            return self
    else:
        return self

cpdef UintSet u24_set_remove(UintSet self, u64 cur, u64 minsize, u64 val):
    cdef UintSet s
    if val <= UINT24_MAX:
        #
        if cur < minsize:
            s=size_choose_u24set(cur)
            copy_to_new_set_n(self, s, cur)
            s._remove(val)
            return s
        else:
            self._remove(val)
            return self
    else:
        return self
    
cpdef UintSet u40_set_remove(UintSet self, u64 cur, u64 minsize, u64 val):
    cdef UintSet s
    if val <= UINT40_MAX:
        #
        if cur < minsize:
            s=size_choose_u40set(cur)
            copy_to_new_set_n(self, s, cur)
            s._remove(val)
            return s
        else:
            self._remove(val)
            return self
    else:
        return self
    
cpdef UintSet u48_set_remove(UintSet self, u64 cur, u64 minsize, u64 val):
    cdef UintSet s
    if val <= UINT48_MAX:
        #
        if cur < minsize:
            s=size_choose_u48set(cur)
            copy_to_new_set_n(self, s, cur)
            s._remove(val)
            return s
        else:
            self._remove(val)
            return self
    else:
        return self
    
cpdef UintSet u64_set_remove(UintSet self, u64 cur, u64 minsize, u64 val):
    cdef UintSet s
    if val <= UINT64_MAX:
        #
        if cur < minsize:
            s=size_choose_u64set(cur)
            copy_to_new_set_n(self, s, cur)
            s._remove(val)
            return s
        else:
            self._remove(val)
            return self
    else:
        return self

        
#-----------------------------------------------------------------------------------------------------------------------
cdef u8 log2(u64 v):
    cdef u64 i, flag=1
    for i in range(1,64):
        if flag<v:
            flag <<= 1
        else:
            return i
    return 64
cdef u8 log128(u64 v):
    cdef u64 i, flag=127
    for i in range(1,9):
        if flag<v:
            flag <<= 7
        else:
            return i
    if v< flag:
        return 9
    else:
        return 10

cdef class IterUintSet:
    cdef readonly UintSet s
    cdef readonly u64 i, count, s_count
    def __init__(self, UintSet s):
        self.s=s
        self.i=0
        self.s_count=s._count()
    cdef inline u64 _next(self):
        cdef u64 i=self.i
        if self.count < self.s_count:
            self.count += 1
            return self.s._next(&self.i)
        else:
            raise 0

#-----------------------------------------------------------------------------------------------------------------------

cdef inline u64 bitset_in(u64* data, u64 val):
    cdef u64 ii = val >> 6, jj = val & 63, flag = ONE << jj
    return data[ii]&flag

cdef inline bitset_set1(u64* data, u64 val):
    cdef u64 ii = val >> 6, jj = val & 63, flag = ONE << jj
    data[ii] |= flag

cdef inline bitset_set0(u64* data, u64 val):
    cdef u64 ii = val >> 6, jj = val & 63, flag = ONE << jj
    data[ii] &= ~flag
cpdef str_bitstring(u64 v):
    cdef char[64+8] s
    cdef u64 i,ii, iii=0
    for i in range(8):
        for ii in range(8):
            s[iii]=c'1' if v&1 else c'0'
            v>>=1
            iii +=1
        s[iii]=c'_'
        iii+=1
    assert iii==64+8
    return PyUnicode_FromStringAndSize(s, 64+8)

cdef u64 ONE=1

cdef inline u64 bitset_add(u64* data, u64 val):
    cdef u64 ii = val >> 6, jj = val & 63, flag = ONE << jj
    #print(f'debug val={val}, jj={jj}, flag={flag}, data[{ii}]={str_bitstring(data[ii])}, bitset add')
    if data[ii] & flag:
        #print(f'bitset add eq')
        return 0
    else:
        data[ii] |= flag
        #print(f'debug data[{ii}]={str_bitstring(data[ii])}, bitset add after')
        return 1

cdef inline u64 bitset_remove(u64* data, u64 val):
    cdef u64 ii = val >> 6, jj = val & 63, flag = ONE << jj
    if data[ii] & flag:
        data[ii] &= ~flag
        return 1
    else:
        return 0
#-----------------------------------------------------------------------------------------------------------------------

cpdef tuple tuple_resize_bigger(tuple tp0, u64 new_size):
    cdef u64 i
    cdef tuple new_tp = PyTuple_New(new_size)
    for i in range(len(tp0)):
        o = <object>PyTuple_GET_ITEM(tp0, i)
        Py_INCREF(tp0)
        PyTuple_SET_ITEM(new_tp, i, o)
    for i in range(len(tp0), new_size):
        PyTuple_SET_ITEM(new_tp, i, None)
    return new_tp

cpdef tuple tuple_resize_smaller(tuple tp0, u64 new_size):
    cdef u64 i
    cdef tuple new_tp = PyTuple_New(new_size)
    for i in range(new_size):
        o = <object>PyTuple_GET_ITEM(tp0, i)
        Py_INCREF(tp0)
        PyTuple_SET_ITEM(new_tp, i, o)
    return new_tp

cdef tuple EMPTY_TUPLE=tuple()


#-----------------------------------------------------------------------------------------------------------------------
cdef get_buffer_array(typecode, u8* data, u64 nbytes):
    cdef array arr = array(typecode)
    resize(arr, <u64>(nbytes/arr.ob_descr.itemsize))
    memcpy(arr.data.as_uchars, data, nbytes)
    return arr
cdef class UintSet:
    cpdef UintSet init(self, u64 log2size): raise NotImplementedError(type(self))
    def __len__(self):return self._cur()
    @property
    def address(self):
        return <u64>self._data()
    cdef u8* _data(self): raise NotImplementedError(type(self))
    cpdef array to_array(self):
        cdef array arr=array(Q)
        resize(arr, self._cur())
        cdef u64 ii, v, i=0
        for ii in range(self._cur()):
            v = self._next(&i)
            arr.data.as_ulonglongs[ii]=v
            i+=1
        return arr
    cpdef get_buffer_array(self, typecode):
        return get_buffer_array(typecode, self._data(), self.nbytes())
    cdef IterUintSet _iter(self):
        return IterUintSet(self)
    cdef u64 _log2size(self):
        raise NotImplementedError(type(self))
    cdef _append(self, u64 val):
        self._insert(val)
    cdef u64 get(self, u64 i):
        raise NotImplementedError(type(self))
    cpdef bint contains(self, u64 val):
        raise NotImplementedError(type(self))
    cpdef u64 get_index(self,u64 val):
        raise NotImplementedError(type(self))
    cdef u64 _next(self, u64* i):
        raise NotImplementedError(type(self))
    cpdef UintSet add(self, u64 val):
        raise NotImplementedError(type(self))
    cdef u64 _insert(self, u64 val,):
        raise NotImplementedError(type(self))
    cdef u64 _remove(self, u64 val):
        raise NotImplementedError(type(self))
    cpdef UintSet remove(self, u64 val):
        raise NotImplementedError(type(self))
    cdef u64 _pop_max_value(self):
        raise NotImplementedError(type(self))
    cdef u8* as_u8s(self):raise NotImplementedError(type(self))
    cdef u16* as_u16s(self):raise NotImplementedError(type(self))
    cdef u32* as_u32s(self):raise NotImplementedError(type(self))
    cdef u64* as_u64s(self):raise NotImplementedError(type(self))
    cdef u64 _itemsize(self):raise NotImplementedError(type(self))
    cdef u64 _max_itemcount(self):raise NotImplementedError(type(self))
    cdef u64 _min_itemcount(self): raise NotImplementedError(type(self))
    cdef u64 _cur(self):raise NotImplementedError(type(self))
    cpdef u64 nbytes(self):
        return self._itemsize()*self._max_itemcount()

cdef u64 MASK_BITSET=UINT64_MAX-7

cdef class UintBitSet(UintSet):
    cdef u64* data
    cdef readonly u64 cur, log2size
    def __cinit__(self):
        self.data=NULL
        self.cur=self.log2size=0
    cdef u8* _data(self,): return <u8*>self.data
    cdef u64 _cur(self):
        return self.cur
    cpdef UintSet init(self, u64 log2size):
        self.data = <u64*>malloc_raise(ONE<<(log2size-3))
        my_memset0(self.data,  ONE<<(log2size-3))
        self.cur=0
        self.log2size=log2size
        return self
    def __dealloc__(self):
        if self.data!=NULL: free(self.data)
    cdef u64 _next(self, u64 * i):
        return next_bitset(self.data, i)
    cdef inline u64 _max_itemcount(self, ): return UINT64_MAX
    cpdef u64 nbytes(self): return (ONE << self.log2size) >> 3
    cdef u64 _insert(self, u64 val):
        #print(f'val={val}, log2={self.log2size}, data={<u64>self.data}, debug uint bitset _insert')
        self.cur+=bitset_add(self.data, val)
        #print('uint bitset _insert ok~')
    cdef u64 _remove(self, u64 val):
        self.cur-=bitset_remove(self.data, val)
    cdef u64 get(self, u64 val):
        return val if bitset_in(self.data, val) else 0
    cpdef bint contains(self, u64 val):
        return bitset_in(self.data, val)!=0
    cpdef u64 get_index(self, u64 val):
        return val if bitset_in(self.data, val) else UINT64_MAX
    cdef u64 pop_max_value(self):
        cdef u64 i, v, end=self._max_itemcount()>>3, ii
        for i in range(self._max_itemcount()):
            if self.data[end-i]==0:continue
            else:break
        #
        v=self.data[end-i]
        v>>=1
        for ii in range(1,64):
            if v!=0:
                v>>=1
            else:
                return (end-i)<<6 + ii
        raise RuntimeError('')
    
cdef class U8BitSet(UintSet):
    cdef readonly u64[4] data
    cdef readonly u8 cur
    cdef u64 _cur(self): return self.cur
    cdef u64 _itemsize(self): return 1
    cdef u64 _next(self, u64 * i):
        return next_bitset(self.data, i)
    cpdef UintSet add(self, u64 val):
        #print(f'debug cur={self.cur}, val={val}, u8 bitset add')
        return u8bitset_add(self, self.cur, val)
    cpdef UintSet remove(self, u64 val):
        return u8_set_remove(self, self.cur, 10, val)
    cpdef u64 nbytes(self): return 32
    def __cinit__(self):
        self.cur=0
        cdef u64 i
        for i in range(4):self.data[i]=0
    cdef u64 _insert(self, u64 val):
        self.cur += bitset_add(self.data, val)
    cdef u64 _remove(self, u64 val):
        #print(f'debug cur={self.cur}, val={val}, u8 bitset _remove')
        self.cur -= bitset_remove(self.data, val)
    cdef u64 get(self, u64 val):
        return val if bitset_in(self.data, val) else 0
    cpdef bint contains(self, u64 val):
        return bitset_in(self.data, val) != 0
    cpdef u64 get_index(self, u64 val):
        return val if bitset_in(self.data, val) else UINT64_MAX
    cdef u64 pop_max_value(self):
        cdef u64 i, v, ii
        for i in range(1,4):
            v=self.data[4-i]
            flag=1
            for ii in range(64):
                if v&flag:
                    return i<<6+ii
        return 0

cdef class U16BitSet(UintBitSet):
    cdef u64 _itemsize(self): return 2
    cpdef UintSet add(self, u64 val):
        return u16bitset_add(self, self.cur, val)
    cpdef UintSet remove(self, u64 val):
        return u16_set_remove(self, self.cur, ONE<<9, val)
    
cdef class U32BitSet(UintBitSet):
    cdef u64 _itemsize(self): return 4
    cpdef UintSet add(self, u64 val):
        return u32bitset_add(self, self.cur, val)
    cpdef UintSet remove(self, u64 val):
        return u32_set_remove(self, self.cur, ONE<<24, val)

cdef class U24BitSet(UintBitSet):
    cdef u64 _itemsize(self): return 3
    cpdef UintSet add(self, u64 val):
        return u40bitset_add(self, self.cur, val)
    cpdef UintSet remove(self, u64 val):
        return u40_set_remove(self, self.cur, ONE << 32, val)

cdef class U40BitSet(UintBitSet):
    cdef u64 _itemsize(self): return 5
    cpdef UintSet add(self, u64 val):
        return u40bitset_add(self, self.cur, val)
    cpdef UintSet remove(self, u64 val):
        return u40_set_remove(self, self.cur, ONE<<32, val)

cdef class U48BitSet(UintBitSet):
    cdef u64 _itemsize(self): return 6
    cpdef UintSet add(self, u64 val):
        return u48bitset_add(self, self.cur, val)
    cpdef UintSet remove(self, u64 val):
        return u48_set_remove(self, self.cur, ONE<<40, val)

cdef class U64BitSet(UintBitSet):
    cdef u64 _itemsize(self): return 8
    cpdef UintSet add(self, u64 val):
        return u64bitset_add(self, self.cur, val)
    cpdef UintSet remove(self, u64 val):
        return u64_set_remove(self, self.cur, ONE<<53, val)


#-----------------------------------------------------------------------------------------------------------------------
cdef class U16Set(UintSet):
    cdef u8 * _data(self): return <u8 *> self.as_u16s()
    cpdef UintSet add(self, u64 val):
        return u16_set_add(self, self._cur(), self._max_itemcount(), val )
    cpdef UintSet remove(self, u64 val):
        return u16_set_remove(self, self._cur(), self._min_itemcount(), val )
    cdef inline u64 _itemsize(self,): return 2

cdef class U16ArraySet(U16Set):
    cdef readonly u8 cur
    cdef inline u64 _cur(self): return self.cur
    cdef u64 _next(self, u64 * i):
        return next_u16_arrayset(self.as_u16s(), i)
    cdef _append(self, u64 val):
        self.as_u16s()[self.cur] = val
        self.cur += 1
    cdef u64 _insert(self, u64 val):
        if bisect_insert_u16(self.as_u16s(), val, self.cur)!=UINT64_MAX:self.cur +=1
    cdef u64 _remove(self, u64 val):
        if bisect_remove_u16(self.as_u16s(), val, self.cur)!=UINT64_MAX:self.cur -= 1
    cpdef bint contains(self, u64 val):
        cdef uint eq
        bisect_u16_in(self.as_u16s(), val, self.cur, &eq)
        return eq == 1
    cpdef u64 get_index(self, u64 val):
        cdef uint eq
        cdef u64 i = bisect_u16_in(self.as_u16s(), val, self.cur, &eq)
        return i if eq else UINT64_MAX
    cdef u64 get(self, u64 i):
        return self.as_u16s()[i]
    cdef u64 _pop_max_value(self):
        self.cur-=1
        return self.as_u16s()[self.cur+1]

cdef class U16HashSet(U16Set):
    cdef u16* data
    cdef readonly u16 cur, mask, log2size
    cdef inline u16* as_u16s(self): return self.data
    cdef inline u64 _cur(self): return self.cur
    cdef inline u64 _mask(self):
        return (ONE << self.log2size) - 1
    cdef inline u64 _max_itemcount(self):return (3*(ONE << self.log2size))>>2
    cdef inline u64 _min_itemcount(self):return (ONE << self.log2size)>>3
    cpdef u64 nbytes(self):
        return self._itemsize()*((ONE<<self.log2size))
    cpdef UintSet init(self, u64 log2size):
        self.log2size=log2size
        self.data = <u16*>py_calloc((ONE << log2size)*self._itemsize())
        assert <u8*>self.data == self._data()
        #print(f'debug hashset data, log2={log2size}, nbytes={self.nbytes()},data={<u64>self.data}', get_buffer_array('H',<u8*>self.data, self.nbytes()))
        #my_memset0(self.data,  self.nbytes())
        #print(f'debug hashset memset data, data={<u64> self.data}', get_buffer_array('H',<u8*>self.data, self.nbytes()))
        self.mask = (ONE << log2size)-1
        self.cur=0
        return self
    def __cinit__(self):
        self.data=NULL
    def __dealloc__(self):
        if self.data !=NULL:
            PyMem_Free(self.data)
    cdef u64 _insert(self, u64 val):
        #print(f'cur={self.cur}, log2={self.log2size}, mask={self.mask}, val={val},  debug u16 hashset _insert')
        if u16_hash_insert(self.data, self.mask, val)!=UINT64_MAX: self.cur+=1
    cdef u64 _remove(self, u64 val):
        if u16_remove_hash(self.data, self.mask, val):self.cur-=1
    cpdef bint contains(self, u64 val):
        return u16_hash_search_in(self.data, self.mask, val)!=UINT64_MAX
    cpdef u64 get_index(self, u64 val):
        return u16_hash_search_in(self.data, self.mask, val)
    cdef u64 get(self, u64 i):
        return self.data[i]
    cdef inline u64 _next(self, u64* iptr):
        return next_u16_hashset(self.data, iptr)
    cdef u64 _pop_max_value(self):
        cdef u64 i,max=0
        if self.cur>0:
            for i in range(self._max_itemcount()):
                v=self.as_u16s()[i]
                max = v if max<v else max
            self.cur-=1
            return max
        else:
            return 0

cdef class U32Set(UintSet):
    cdef u8* _data(self): return <u8*>self.as_u32s()
    cpdef UintSet add(self, u64 val):
        return u32_set_add(self, self._cur(), self._max_itemcount(), val )
    cpdef UintSet remove(self, u64 val):
        return u32_set_remove(self, self._cur(), self._min_itemcount(), val )
    cdef inline u64 _itemsize(self,): return 4

cdef class U32ArraySet(U32Set):
    cdef readonly u8 cur
    cdef u32* as_u32s(self):return <u32*>self._data()
    cdef inline u64 _cur(self): return self.cur
    cdef u64 _next(self, u64 * i):
        return next_u32_arrayset(self.as_u32s(), i)
    cdef _append(self, u64 val):
        self.as_u32s()[self.cur] = val
        self.cur += 1
    cdef u64 _insert(self, u64 val):
        if bisect_insert_u32(self.as_u32s(), val, self.cur)!=UINT64_MAX:self.cur +=1
    cdef u64 _remove(self, u64 val):
        if bisect_remove_u32(self.as_u32s(), val, self.cur)!=UINT64_MAX:self.cur -= 1
    cpdef bint contains(self, u64 val):
        cdef uint eq
        bisect_u32_in(self.as_u32s(), val, self.cur, &eq)
        return eq==1
    cpdef u64 get_index(self, u64 val):
        cdef uint eq
        cdef u64 i = bisect_u32_in(self.as_u32s(), val, self.cur, &eq)
        return i if eq else UINT64_MAX
    cdef u64 get(self, u64 i):
        return self.as_u32s()[i]
    cdef u64 _pop_max_value(self):
        self.cur-=1
        return self.as_u32s()[self.cur+1]

cdef class U32HashSet(U32Set):
    cdef u32* data
    cdef readonly u32 cur, log2size, mask
    cdef u32* as_u32s(self): return self.data
    cpdef u64 nbytes(self):
        return self._itemsize() * (ONE << self.log2size)
    cdef inline u64 _cur(self): return self.cur
    cdef inline u64 _mask(self):
        return (ONE << self.log2size) - 1
    cdef inline u64 _max_itemcount(self):
        return (3 * (ONE << self.log2size)) >> 2
    cdef inline u64 _min_itemcount(self):
        return (ONE << self.log2size) >> 3
    cpdef UintSet init(self, u64 log2size):
        self.data = <u32*>py_calloc((ONE << log2size)*self._itemsize())
        assert <u8 *> self.data == self._data()
        self.log2size=log2size
        ##print(f'debug hashset data, log2={log2size}, nbytes={self.nbytes()},data={<u64> self.data}',get_buffer_array('L', <u8 *> self.data, self.nbytes()))
        #my_memset0(self.data,  self.nbytes())
        ##print(f'debug hashset memset data, data={<u64> self.data}', get_buffer_array('L', <u8 *> self.data, self.nbytes()))
        self.mask = (ONE << log2size) - 1
        self.cur = 0
        return self
    def __cinit__(self):
        self.data=NULL
    def __dealloc__(self):
        if self.data !=NULL:
            PyMem_Free(self.data)
    cdef u64 _insert(self, u64 val):
        if u32_hash_insert(self.data, self.mask, val)!=UINT64_MAX: self.cur+=1
    cdef u64 _remove(self, u64 val):
        if u32_remove_hash(self.data, self.mask, val)!=UINT64_MAX:self.cur-=1
    cpdef bint contains(self, u64 val):
        return u32_hash_search_in(self.data, self.mask, val)!=UINT64_MAX
    cpdef u64 get_index(self, u64 val):
        return u32_hash_search_in(self.data, self.mask, val)
    cdef u64 get(self, u64 i):
        return self.data[i]
    cdef inline u64 _next(self, u64* iptr):
        return next_u32_hashset(self.data, iptr)
    cdef u64 _pop_max_value(self):
        cdef u64 i,max=0
        if self.cur>0:
            for i in range(self._max_itemcount()):
                v=self.as_u32s()[i]
                max = v if max<v else max
            self.cur-=1
            return max
        else:
            return 0

cdef class U24Set(UintSet):
    cdef u16 * as_low16s(self):
        return <u16*> self._data()
    cpdef UintSet add(self, u64 val):
        return u24_set_add(self, self._cur(), self._max_itemcount(), val)
    cpdef UintSet remove(self, u64 val):
        return u24_set_remove(self, self._cur(), self._min_itemcount(), val)
    cdef inline u64 _itemsize(self, ):
        return 3

cdef class U24ArraySet(U24Set):
    cdef readonly u8 cur
    cdef u64 _next(self, u64* i):
        return next_u24_arrayset(self.as_low16s(), self.as_high8s(), i)
    cdef inline u64 _cur(self):
        return self.cur
    cdef _append(self, u64 val):
        self.as_low16s()[self.cur] = val & UINT16_MAX
        self.as_high8s()[self.cur] = val >> 16
        self.cur += 1
    cdef u8 * as_high8s(self):
        return self._data() + (self._max_itemcount() << 1)
    cdef u64 _insert(self, u64 val):
        cdef u64 i = bisect_insert_u24(self.as_low16s(), self.as_high8s(), val, self.cur)
        if i != UINT64_MAX: self.cur += 1
        return i
    cdef u64 _remove(self, u64 val):
        cdef u64 i = bisect_remove_u24(self.as_low16s(), self.as_high8s(), val, self.cur)
        if i != UINT64_MAX: self.cur += 1
        return i
    cdef u64 get(self, u64 i):
        return self.as_low16s()[i] + self.as_high8s()[i] << 16
    cpdef bint contains(self, u64 val):
        cdef uint eq
        bisect_u24_in(self.as_low16s(), self.as_high8s(), val, self.cur, &eq)
        return eq == 1
    cpdef u64 get_index(self, u64 val):
        cdef uint eq
        cdef u64 i = bisect_u24_in(self.as_low16s(), self.as_high8s(), val, self.cur, &eq)
        return i if eq else UINT64_MAX
    cdef u64 _pop_max_value(self):
        self.cur -= 1
        return self.get(self.cur + 1)


cdef class U24HashSet(U24Set):
    cdef u16* data
    cdef readonly u64 mask
    cdef readonly u32 cur, log2size
    cpdef u64 nbytes(self):
        return self._itemsize() * (ONE << self.log2size)
    cdef inline u16* as_low16s(self): return self.data
    cdef inline u8* _data(self): return <u8*>self.data
    cpdef UintSet init(self, u64 log2size):
        self.data = <u16*>py_calloc((ONE << log2size)*self._itemsize())
        self.log2size = log2size

        self.mask=(ONE << log2size)-1
        self.cur=0
        return self
    def __cinit__(self):
        self.data=NULL
    def __dealloc__(self):
        if self.data !=NULL:
            PyMem_Free(self.data)
    cdef inline u64 _cur(self): return self.cur
    cdef inline u8 * as_high8s(self): return <u8 *> (self.data + (ONE<<self.log2size))
    cdef inline u64 _max_itemcount(self):
        return (3 * (ONE << self.log2size)) >> 2
    cdef inline u64 _min_itemcount(self):
        return (ONE << self.log2size) >> 3
    cdef inline u64 _mask(self):
        return (ONE << self.log2size) - 1
    cdef u64 _insert(self, u64 val):
        cdef u64 i=u24_hash_insert(self.data, self.as_high8s(), (ONE << self.log2size)-1, val)
        if i!=UINT64_MAX: self.cur += 1
        return i
    cdef u64 _remove(self, u64 val):
        cdef u64 i=u24_remove_hash(self.data, self.as_high8s(), (ONE << self.log2size)-1, val)
        if i!=UINT64_MAX: self.cur += 1
        return i
    cpdef bint contains(self, u64 val):
        return u24_hash_search_in(self.data, self.as_high8s(), (ONE << self.log2size)-1, val)!=UINT64_MAX
    cpdef u64 get_index(self, u64 val):
        return u24_hash_search_in(self.data, self.as_high8s(), self.mask, val)
    cdef u64 get(self, u64 i):
        return self.data[i] + self.as_high8s()[i]<<16
    cdef inline u64 _next(self, u64 * iptr):
        return next_u24_hashset(self.data, self.as_high8s(), iptr)
    cdef u64 _pop_max_value(self):
        cdef u64 i, max = 0
        if self.cur > 0:
            for i in range(self._max_itemcount()):
                v = self.as_u16s()[i]
                max = v if max < v else max
            self.cur -= 1
            return max
        else:
            return 0

cdef class U40Set(UintSet):
    cdef u32 * as_low32s(self): return <u32*> self._data()
    cpdef UintSet add(self, u64 val):
        if u40_set_add(self, self._cur(), self._max_itemcount(), val )!=UINT64_MAX:
            self.cur += 1
    cpdef UintSet remove(self, u64 val):
        if u40_set_remove(self, self._cur(), self._min_itemcount(), val )!=UINT64_MAX:
            self.cur +=1
    cdef inline u64 _itemsize(self,): return 5
    

cdef class U40ArraySet(U40Set):
    cdef readonly u8 cur
    cdef u64 _next(self, u64 * i):
        return next_u40_arrayset(self.as_low32s(), self.as_high8s(), i)
    cdef inline u64 _cur(self): return self.cur
    cdef _append(self, u64 val):
        self.as_low32s()[self.cur] = val&UINT32_MAX
        self.as_high8s()[self.cur] =  val>>32
        self.cur += 1
    cdef u8* as_high8s(self):return self._data()+(self._max_itemcount()<<2)
    cdef u64 _insert(self, u64 val):
        cdef u64 i=bisect_insert_u40(self.as_low32s(), self.as_high8s(), val, self.cur)
        if i!=UINT64_MAX: self.cur += 1
        return i
    cdef u64 _remove(self, u64 val):
        cdef u64 i=bisect_remove_u40(self.as_low32s(), self.as_high8s(), val, self.cur)
        if i!=UINT64_MAX: self.cur += 1
        return i
    cdef u64 get(self, u64 i):
        return self.as_low32s()[i]+self.as_high8s()[i]<<32
    cpdef bint contains(self, u64 val):
        cdef uint eq
        bisect_u40_in(self.as_low32s(), self.as_high8s(), val, self.cur, &eq)
        return eq==1
    cpdef u64 get_index(self, u64 val):
        cdef uint eq
        cdef u64 i=bisect_u40_in(self.as_low32s(), self.as_high8s(), val, self.cur, &eq)
        return i if eq else UINT64_MAX
    cdef u64 _pop_max_value(self):
        self.cur-=1
        return self.get(self.cur+1)


cdef class U40HashSet(U40Set):
    cdef u32* data
    cdef readonly u64 cur, log2size, mask
    cpdef u64 nbytes(self):
        return self._itemsize() * (ONE << self.log2size)
    cdef u8* _data(self): return <u8*>self.data
    cdef u32* as_low32s(self): return self.data
    cpdef UintSet init(self, u64 log2size):
        self.data = <u32*>py_calloc((ONE << log2size)*self._itemsize())
        #my_memset0(self.data,  self.nbytes())
        self.log2size = log2size
        self.mask=(ONE << log2size)-1
        self.cur=0
        return self
    def __cinit__(self):
        self.data=NULL
    def __dealloc__(self):
        if self.data !=NULL:
            PyMem_Free(self.data)
    cdef inline u64 _cur(self): return self.cur
    cdef inline u8 * as_high8s(self): return <u8 *> (self.data + (ONE<<self.log2size))
    cdef inline u64 _max_itemcount(self):
        return (3 * (ONE << self.log2size)) >> 2
    cdef inline u64 _min_itemcount(self):
        return (ONE << self.log2size) >> 3
    cdef inline u64 _mask(self):
        return (ONE << self.log2size) - 1
    cdef u64 _insert(self, u64 val):
        cdef u64 i=u40_hash_insert(self.data, self.as_high8s(), (ONE << self.log2size)-1, val)
        if i!=UINT64_MAX: self.cur += 1
        return i
    cdef u64 _remove(self, u64 val):
        cdef u64 i=u40_remove_hash(self.data, self.as_high8s(), (ONE << self.log2size)-1, val)
        if i!=UINT64_MAX: self.cur += 1
        return i
    cpdef bint contains(self, u64 val):
        return u40_hash_search_in(self.data, self.as_high8s(), (ONE << self.log2size)-1, val)!=UINT64_MAX
    cpdef u64 get_index(self, u64 val):
        return u32_hash_search_in(self.data, self.mask, val)
    cdef u64 get(self, u64 i):
        return self.data[i] + self.as_high8s()[i]<<32
    cdef inline u64 _next(self, u64 * iptr):
        return next_u40_hashset(self.data, self.as_high8s(), iptr)
    cdef u64 _pop_max_value(self):
        cdef u64 i, max = 0
        if self.cur > 0:
            for i in range(self._max_itemcount()):
                v = self.as_u32s()[i]
                max = v if max < v else max
            self.cur -= 1
            return max
        else:
            return 0
    
cdef class U48Set(UintSet):
    cdef u32* as_low32s(self): return <u32*> self._data()
    cpdef UintSet add(self, u64 val):
        return u48_set_add(self, self._cur(), self._max_itemcount(), val )
    cpdef UintSet remove(self, u64 val):
        return u48_set_remove(self, self._cur(), self._min_itemcount(), val )
    cdef inline u64 _itemsize(self,): return 6


cdef class U48ArraySet(U48Set):
    cdef readonly u8 cur
    cdef u8 * _data(self): return <u8 *> self.as_u32s()
    cdef inline u64 _cur(self): return self.cur
    cdef u64 _next(self, u64 * i):
        return next_u48_arrayset(self.as_low32s(), self.as_high16s(), i)
    cdef u16 * as_high16s(self): return <u16*>(self._data() + (self._max_itemcount() << 2))
    cdef _append(self, u64 val):
        self.as_low32s()[self.cur] = val & UINT32_MAX
        self.as_high16s()[self.cur] = val >> 32
        self.cur += 1
    cdef u64 _insert(self, u64 val):
        cdef u64 i=bisect_insert_u48(self.as_low32s(), self.as_high16s(), val, self.cur)
        if i!=UINT64_MAX: self.cur += 1
        return i
    cdef u64 _remove(self, u64 val):
        cdef u64 i=bisect_remove_u48(self.as_low32s(), self.as_high16s(), val, self.cur)
        if i!=UINT64_MAX: self.cur += 1
        return i
    cdef u64 get(self, u64 i):
        return self.as_low32s()[i] + self.as_high16s()[i] << 32
    cpdef bint contains(self, u64 val):
        cdef uint eq
        bisect_u48_in(self.as_low32s(), self.as_high16s(), val, self.cur, &eq)
        return eq==1
    cpdef u64 get_index(self, u64 val):
        cdef uint eq
        cdef u64 i = bisect_u48_in(self.as_low32s(), self.as_high16s(), val, self.cur, &eq)
        return i if eq else UINT64_MAX
    cdef u64 _pop_max_value(self):
        self.cur -= 1
        return self.get(self.cur + 1)
    
cdef class U48HashSet(U48Set):
    cdef u32* data
    cdef readonly u64 cur, mask, log2size
    cdef u8 * _data(self):
        return <u8 *> self.data
    cpdef u64 nbytes(self):
        return self._itemsize() * (ONE << self.log2size)
    cpdef UintSet init(self, u64 log2size):
        self.data = <u32*>py_calloc((ONE << log2size)*self._itemsize())
        #my_memset0(self.data,  self.nbytes())
        self.log2size = log2size
        self.mask = (ONE << log2size) - 1
        self.cur=0
        return self
    def __cinit__(self):
        self.data=NULL
    def __dealloc__(self):
        if self.data !=NULL:
            PyMem_Free(self.data)
    cdef inline u64 _mask(self): return (ONE << self.log2size) - 1
    cdef inline u64 _cur(self): return self.cur
    cdef inline u16 * as_high16s(self): return <u16*>(self.data + (ONE<<self.log2size) )
    cdef inline u64 _max_itemcount(self): return (3 * (ONE << self.log2size)) >> 2
    cdef inline u64 _min_itemcount(self): return (ONE << self.log2size) >> 3
    cdef u64 _insert(self, u64 val):
        cdef u64 i=u48_hash_insert(self.data, self.as_high16s(), (ONE << self.log2size)-1, val)
        if i!=UINT64_MAX: self.cur += 1
        return i
    cdef u64 _remove(self, u64 val):
        cdef u64 i=u48_remove_hash(self.data, self.as_high16s(), (ONE << self.log2size)-1, val)
        if i!=UINT64_MAX: self.cur += 1
        return i
    cpdef bint contains(self, u64 val):
        return u48_hash_search_in(self.data, self.as_high16s(), (ONE << self.log2size)-1, val)!=UINT64_MAX
    cpdef u64 get_index(self, u64 val):
        return u48_hash_search_in(self.data, self.as_high16s(), (ONE << self.log2size)-1, val)
    cdef u64 get(self, u64 i):
        return self.data[i]
    cdef inline u64 _next(self, u64* iptr):
        return next_u48_hashset(self.data, self.as_u16s(), iptr)
    cdef u64 _pop_max_value(self):
        cdef u64 i =self.cur
        self.cur -= 1
        cdef u64 v = self.data[i] + self.as_high16s()[i] << 32
        self.data[i] = 0
        self.as_high16s()[i] = 0
        return v

cdef class U64Set(UintSet):
    cpdef UintSet add(self, u64 val):
        return u64_set_add(self, self._cur(), self._max_itemcount(), val )
    cpdef UintSet remove(self, u64 val):
        return u64_set_remove(self, self._cur(), self._min_itemcount(), val )
    cdef inline u64 _itemsize(self, ): return 8

cdef class U64ArraySet(U64Set):
    cdef readonly u8 cur
    cdef inline u64 _cur(self): return self.cur
    cdef u64 _next(self, u64 * i):
        return next_u64_arrayset(self.as_u64s(), i)
    cdef _append(self, u64 val):
        self.as_u64s()[self.cur] = val
        self.cur += 1
    cdef u64 _insert(self, u64 val):
        if bisect_insert_u64(self.as_u64s(), val, self.cur)!=UINT64_MAX:self.cur +=1
    cdef u64 _remove(self, u64 val):
        if bisect_remove_u64(self.as_u64s(), val, self.cur)!=UINT64_MAX:self.cur -= 1
    cpdef bint contains(self, u64 val):
        cdef uint eq
        bisect_u64_in(self.as_u64s(), val, self.cur, &eq)
        return eq==1
    cpdef u64 get_index(self, u64 val):
        cdef uint eq
        cdef u64 i = bisect_u64_in(self.as_u64s(), val, self.cur, &eq)
        return i if eq else UINT64_MAX
    cdef u64 get(self, u64 i):
        return self.as_u64s()[i]
    cdef u64 _pop_max_value(self):
        self.cur-=1
        return self.as_u64s()[self.cur+1]

cdef class U64HashSet(U64Set):
    cdef u64* data
    cdef readonly u64 cur, log2size, mask
    cpdef u64 nbytes(self):
        return self._itemsize() * (ONE << self.log2size)
    cdef u8* _data(self): return <u8*>self.data
    cdef inline u64 _cur(self): return self.cur
    cdef inline u64 _mask(self): return (ONE << self.log2size)-1
    cdef inline u64 _max_itemcount(self):
        return (3 * (ONE << self.log2size)) >> 2
    cdef inline u64 _min_itemcount(self):
        return (ONE << self.log2size) >> 3
    cpdef UintSet init(self, u64 log2size):
        self.data = <u64*>py_calloc((ONE << log2size)*self._itemsize())
        #my_memset0(self.data,  self.nbytes())
        self.log2size = log2size
        self.mask = (ONE << log2size)-1
        self.cur=0
        return self
    def __cinit__(self):
        self.data=NULL
    def __dealloc__(self):
        if self.data !=NULL:
            PyMem_Free(self.data)
    cdef u64 _insert(self, u64 val):
        if u64_hash_insert(self.data, self.mask, val)!=UINT64_MAX: self.cur+=1
    cdef u64 _remove(self, u64 val):
        if u64_remove_hash(self.data, self.mask, val):self.cur-=1
    cpdef bint contains(self, u64 val):
        return u64_hash_search_in(self.data, self.mask, val)!=UINT64_MAX
    cpdef u64 get_index(self, u64 val):
        return u64_hash_search_in(self.data, self.mask, val)
    cdef u64 get(self, u64 i):
        return self.data[i]
    cdef inline u64 _next(self, u64* iptr):
        return next_u64_hashset(self.data, iptr)
    cdef u64 _pop_max_value(self):
        cdef u64 i,max=0
        if self.cur>0:
            for i in range(self._max_itemcount()):
                v=self.as_u64s()[i]
                max = v if max<v else max
            self.cur-=1
            return max
        else:
            return 0



#-----------------------------------------------uuu16------------------------------------------------------------
cpdef UintSet size_choose_u8set(u64 cur):
    cdef UintSet s
    cdef u64 log2size
    if cur<15:
        if cur>7:
            return U8ArraySet15()
        else:
            return U8ArraySet7()
    else:
        return U8BitSet()
        

cdef class U8ArraySet(UintSet):
    cdef readonly u8 cur
    def __cinit__(self):self.cur=0
    cdef inline u8* _data(self): return self.as_u8s()
    cdef u64 _next(self, u64 * i):
        return next_u8_arrayset(self.as_u8s(), i)
    cdef _append(self, u64 val):
        self.as_u8s()[self.cur]=val
        self.cur+=1
        #print(self.cur, val, 'debug _append u8')
    cdef inline u64 _cur(self):
        return self.cur
    cpdef UintSet add(self, u64 val):
        return u8_set_add(self, self.cur, self._max_itemcount(), val)
    cpdef UintSet remove(self, u64 val):
        return u8_set_remove(self, self.cur, self._max_itemcount(), val)
    cdef u64 _insert(self, u64 val):
        if bisect_insert_u8(self.as_u8s(), val, self.cur) != UINT64_MAX: self.cur += 1
    cdef u64 _remove(self, u64 val):
        if bisect_remove_u8(self.as_u8s(), val, self.cur) != UINT64_MAX: self.cur -= 1
    cpdef bint contains(self, u64 val):
        cdef uint eq
        bisect_u8_in(self.as_u8s(), val, self.cur, &eq)
        return eq==1
    cpdef u64 get_index(self, u64 val):
        cdef uint eq
        cdef u64 i=bisect_u8_in(self.as_u8s(), val, self.cur, &eq)
        return i if eq else UINT64_MAX
    cdef u64 get(self, u64 i):
        return self.as_u8s()[i]
    cdef u64 _pop_max_value(self):
        self.cur -= 1
        return self.as_u8s()[self.cur + 1]

cdef class U8ArraySet7(U8ArraySet):
    cdef readonly u8[7] data
    cdef inline u8 * as_u8s(self): return self.data
    cdef inline u64 _max_itemcount(self): return 7 
    cdef inline u64 _min_itemcount(self): return 0
    
cdef class U8ArraySet15(U8ArraySet):
    cdef readonly u8[15] data
    cdef u8 * as_u8s(self): return self.data
    cdef inline u64 _max_itemcount(self): return 15
    cdef inline u64 _min_itemcount(self): return 4
    
    
#-----------------------------------------------uuu16------------------------------------------------------------
cdef tuple u16arraysets = (U16ArraySet7, U16ArraySet15, U16ArraySet23, U16ArraySet31, U16ArraySet39)
cpdef UintSet size_choose_u16set(u64 cur):
    cdef UintSet s
    cdef u64 log2size
    if cur < 31:
        if cur < 15:
            if cur > 7:
                s = U16ArraySet15()
            else:
                s = U16ArraySet7()
        elif cur < 23:
            s = U16ArraySet23()
        else:
            s = U16ArraySet31()
    elif cur < 39:
        s = U16ArraySet39()
    else:
        log2size = log2(cur)
        log2size = log2size if cur < 3 * (ONE << (log2size - 2)) else log2size + 1
        if log2size < 12:
            s = U16HashSet().init(log2size)
        else:
            return U16BitSet().init(16)
    return s

cdef class U16ArraySet7(U16ArraySet):
    cdef readonly u16[7] data
    cdef inline u16 * as_u16s(self):
        return <u16 *> self.data
    cdef inline u64 _max_itemcount(self): return 7
    cdef inline u64 _min_itemcount(self): return 0

cdef class U16ArraySet15(U16ArraySet):
    cdef readonly u16[15] data
    cdef inline u16 * as_u16s(self):
        return <u16*>self.data
    cdef inline u64 _max_itemcount(self): return 15
    cdef inline u64 _min_itemcount(self): return 4

cdef class U16ArraySet23(U16ArraySet):
    cdef readonly u16[23] data
    cdef inline u16 * as_u16s(self):
        return <u16 *> self.data
    cdef inline u64 _max_itemcount(self): return 23
    cdef inline u64 _min_itemcount(self): return 10

cdef class U16ArraySet31(U16ArraySet):
    cdef readonly u16[31] data
    cdef inline u16 * as_u16s(self):
        return <u16 *> self.data
    cdef inline u64 _max_itemcount(self): return 31
    cdef inline u64 _min_itemcount(self): return 20

cdef class U16ArraySet39(U16ArraySet):
    cdef readonly u16[39] data
    cdef inline u16 * as_u16s(self):
        return <u16 *> self.data
    cdef inline u64 _max_itemcount(self): return 39
    cdef inline u64 _min_itemcount(self): return 27

#-----------------------------------------------uuu32------------------------------------------------------------
cdef tuple u32arraysets = (U32ArraySet3, U32ArraySet7, U32ArraySet15, U32ArraySet23, U32ArraySet31)
cpdef UintSet size_choose_u32set(u64 cur):
    cdef UintSet s
    cdef u64 log2size
    if cur < 23:
        if cur < 7:
            if cur > 3:
                s = U32ArraySet7()
            else:
                s = U32ArraySet3()
        elif cur < 15:
            s = U32ArraySet15()
        else:
            s = U32ArraySet23()
    elif cur < 31:
        s = U32ArraySet31()
    else:
        log2size = log2(cur)
        log2size = log2size if cur < 3 * (ONE << (log2size - 2)) else log2size + 1
        if log2size < 27:
            s = U32HashSet().init(log2size)
        else:
            return U32BitSet().init(32)
    return s

cdef class U32ArraySet3(U32ArraySet):
    cdef readonly u32[3] data
    cdef inline u32 * as_u32s(self):
        return <u32 *> self.data
    cdef inline u64 _max_itemcount(self): return 3
    cdef inline u64 _min_itemcount(self): return 0

cdef class U32ArraySet7(U32ArraySet):
    cdef readonly u32[7] data
    cdef inline u32 * as_u32s(self):
        return <u32 *> self.data
    cdef inline u64 _max_itemcount(self): return 7
    cdef inline u64 _min_itemcount(self): return 2

cdef class U32ArraySet15(U32ArraySet):
    cdef readonly u32[15] data
    cdef inline u32 * as_u32s(self):
        return <u32 *> self.data
    cdef inline u64 _max_itemcount(self): return 15
    cdef inline u64 _min_itemcount(self): return 5

cdef class U32ArraySet23(U32ArraySet):
    cdef readonly u32[23] data
    cdef inline u32 * as_u32s(self):
        return <u32 *> self.data
    cdef inline u64 _max_itemcount(self): return 23
    cdef inline u64 _min_itemcount(self): return 10

cdef class U32ArraySet31(U32ArraySet):
    cdef readonly u32[31] data
    cdef inline u32 * as_u32s(self):
        return <u32 *> self.data
    cdef inline u64 _max_itemcount(self): return 31
    cdef inline u64 _min_itemcount(self): return 18

#-----------------------------------------------uuu24------------------------------------------------------------
cdef tuple u24arraysets = (U24ArraySet5, U24ArraySet13, U24ArraySet21, U24ArraySet29, U24ArraySet37)
cpdef UintSet size_choose_u24set(u64 cur):
    cdef UintSet s
    cdef u64 log2size
    if cur < 29:
        if cur < 13:
            if cur > 3:
                s = U24ArraySet13()
            else:
                s = U24ArraySet5()
        elif cur < 21:
            s = U24ArraySet21()
        else:
            s = U24ArraySet29()
    elif cur < 37:
        s = U24ArraySet37()
    else:
        log2size = log2(cur)
        log2size = log2size if cur < 3 * (ONE << (log2size - 2)) else log2size + 1
        if log2size < 35:
            s = U24HashSet().init(log2size)
        else:
            return U24BitSet().init(24)
    return s
cdef class U24ArraySet5(U24ArraySet):
    cdef readonly u8[15] data
    cdef inline u8 * _data(self):
        return self.data
    cdef inline u64 _max_itemcount(self): return 5
    cdef inline u64 _min_itemcount(self): return 0
    
cdef class U24ArraySet13(U24ArraySet):
    cdef readonly u8[39] data
    cdef inline u8 * _data(self):
        return self.data
    cdef inline u64 _max_itemcount(self): return 13
    cdef inline u64 _min_itemcount(self): return 2
    
cdef class U24ArraySet21(U24ArraySet):
    cdef readonly u8[63] data
    cdef inline u8 * _data(self):
        return self.data
    cdef inline u64 _max_itemcount(self): return 31
    cdef inline u64 _min_itemcount(self): return 9
    
cdef class U24ArraySet29(U24ArraySet):
    cdef readonly u8[87] data
    cdef inline u8 * _data(self):
        return self.data
    cdef inline u64 _max_itemcount(self): return 29
    cdef inline u64 _min_itemcount(self): return 22
    
cdef class U24ArraySet37(U24ArraySet):
    cdef readonly u8[111] data
    cdef inline u8 * _data(self):
        return self.data
    cdef inline u64 _max_itemcount(self): return 37
    cdef inline u64 _min_itemcount(self): return 25
#-----------------------------------------------uuu40------------------------------------------------------------
cdef tuple u40arraysets = (U40ArraySet3, U40ArraySet8, U40ArraySet14, U40ArraySet22, U40ArraySet31)
cpdef UintSet size_choose_u40set(u64 cur):
    cdef UintSet s
    cdef u64 log2size
    if cur < 22:
        if cur < 8:
            if cur > 3:
                s = U40ArraySet8()
            else:
                s = U40ArraySet3()
        elif cur < 14:
            s = U40ArraySet14()
        else:
            s = U40ArraySet22()
    elif cur < 31:
        s = U40ArraySet31()
    else:
        log2size = log2(cur)
        log2size = log2size if cur < 3 * (ONE << (log2size - 2)) else log2size + 1
        if log2size < 35:
            s = U40HashSet().init(log2size)
        else:
            return U40BitSet().init(40)
    return s

cdef class U40ArraySet3(U40ArraySet):
    cdef readonly u8[15] data
    cdef inline u8 * _data(self):
        return self.data
    cdef inline u64 _max_itemcount(self): return 3
    cdef inline u64 _min_itemcount(self): return 0
    

cdef class U40ArraySet8(U40ArraySet):
    cdef readonly u8[40] data
    cdef inline u8 * _data(self):
        return self.data
    cdef inline u64 _max_itemcount(self): return 8
    cdef inline u64 _min_itemcount(self): return 2

cdef class U40ArraySet14(U40ArraySet):
    cdef readonly u8[70] data
    cdef inline u8 * _data(self):
        return self.data
    cdef inline u64 _max_itemcount(self): return 14
    cdef inline u64 _min_itemcount(self): return 5

cdef class U40ArraySet22(U40ArraySet):
    cdef readonly u8[110] data
    cdef inline u8 * _data(self):
        return self.data
    cdef inline u64 _max_itemcount(self): return 22
    cdef inline u64 _min_itemcount(self): return 11


cdef class U40ArraySet31(U40ArraySet):
    cdef readonly u8[155] data
    cdef inline u8 * _data(self):
        return self.data
    cdef inline u64 _max_itemcount(self): return 31
    cdef inline u64 _min_itemcount(self): return 18

 #-----------------------------------------------uuu48------------------------------------------------------------
cdef tuple u48arraysets = (U48ArraySet6, U48ArraySet10, U48ArraySet14, U48ArraySet21, U48ArraySet29)
cpdef UintSet size_choose_u48set(u64 cur):
    cdef UintSet s
    cdef u64 log2size
    if cur < 21:
        if cur < 10:
            if cur > 6:
                s = U48ArraySet10()
            else:
                s = U48ArraySet6()
        elif cur < 14:
            s = U48ArraySet14()
        else:
            s = U48ArraySet21()
    elif cur < 29:
        s = U48ArraySet29()
    else:
        log2size = log2(cur)
        log2size = log2size if cur < 3 * (ONE << (log2size - 2)) else log2size + 1
        if log2size < 43:
            s = U48HashSet().init(log2size)
        else:
            return U48BitSet().init(48)
    return s

cdef class U48ArraySet6(U48ArraySet):
    cdef readonly u8[36] data
    cdef inline u8 * _data(self):
        return self.data
    cdef inline u64 _max_itemcount(self): return 6
    cdef inline u64 _min_itemcount(self): return 0

cdef class U48ArraySet10(U48ArraySet):
    cdef readonly u8[60] data
    cdef inline u8 * _data(self):
        return self.data
    cdef inline u64 _max_itemcount(self): return 10
    cdef inline u64 _min_itemcount(self): return 3

cdef class U48ArraySet14(U48ArraySet):
    cdef readonly u8[84] data
    cdef inline u8 * _data(self):
        return self.data
    cdef inline u64 _max_itemcount(self): return 14
    cdef inline u64 _min_itemcount(self): return 8

cdef class U48ArraySet21(U48ArraySet):
    cdef readonly u8[126] data
    cdef inline u8 * _data(self):
        return self.data
    cdef inline u64 _max_itemcount(self): return 21
    cdef inline u64 _min_itemcount(self): return 12

cdef class U48ArraySet29(U48ArraySet):
    cdef readonly u8[174] data
    cdef inline u8 * _data(self):
        return self.data
    cdef inline u64 _max_itemcount(self): return 29
    cdef inline u64 _min_itemcount(self): return 17


#-----------------------------------------------uuu64------------------------------------------------------------
cdef tuple u64arraysets = (U64ArraySet4, U64ArraySet8, U64ArraySet16, U64ArraySet24, U64ArraySet32)
cpdef UintSet size_choose_u64set(u64 cur):
    cdef UintSet s
    cdef u64 log2size
    if cur < 24:
        if cur < 8:
            if cur > 4:
                s = U64ArraySet8()
            else:
                s = U64ArraySet4()
        elif cur < 16:
            s = U64ArraySet16()
        else:
            s = U64ArraySet24()
    elif cur < 32:
        s = U64ArraySet32()
    else:
        log2size = log2(cur)
        log2size = log2size if cur < 3 * (ONE << (log2size - 2)) else log2size + 1
        if log2size < 58:
            s = U64HashSet().init(log2size)
        else:
            return U64BitSet().init(64)
    return s
#-----------------------------------------------uuu64------------------------------------------------------------
cdef class U64ArraySet4(U64ArraySet):
    cdef  readonly u64[4] data
    cdef inline u64 * as_u64s(self):
        return <u64 *> self.data
    cdef inline u64 _max_itemcount(self): return 4
    cdef inline u64 _min_itemcount(self): return 0
    

cdef class U64ArraySet8(U64ArraySet):
    cdef  readonly u64[8] data
    cdef inline u64 * as_u64s(self):
        return <u64 *> self.data
    cdef inline u64 _max_itemcount(self): return 8
    cdef inline u64 _min_itemcount(self): return 2
    

cdef class U64ArraySet16(U64ArraySet):
    cdef  readonly u64[16] data
    cdef inline u64 * as_u64s(self):
        return <u64 *> self.data
    cdef inline u64 _max_itemcount(self): return 16
    cdef inline u64 _min_itemcount(self): return 6

cdef class U64ArraySet24(U64ArraySet):
    cdef  readonly u64[24] data
    cdef inline u64 * as_u64s(self):
        return <u64 *> self.data
    cdef inline u64 _max_itemcount(self): return 24
    cdef inline u64 _min_itemcount(self): return 12

cdef class U64ArraySet32(U64ArraySet):
    cdef  readonly u64[32] data
    cdef inline u64 * as_u64s(self):
        return <u64 *> self.data
    cdef inline u64 _max_itemcount(self): return 32
    cdef inline u64 _min_itemcount(self): return 20
    

#----------------------------------------------------test--------------------------------------------------

def test_set8():
    cdef u64 i
    cdef UintSet s=U8ArraySet7()
    for i in range(1,8):
        #print(i,'test8')
        s=s.add(i)
        assert s.contains(i)
    #print('u8set7, ok')
    for i in range(8, 16):
        s=s.add(i)
        assert s.contains(i)
    #print('u8set15, ok')
    for i in range(16,256):
        s=s.add(i)
        assert s.contains(i)
    #print('u8bitset, ok')
    for i in range(1,256):
        s=s.remove(i)
        assert not s.contains(i)
    #print('u8remove,ok')

def test_set16():
    cdef u64 i
    cdef UintSet s = U16ArraySet7()
    for i in range(ONE<<16):
        s = s.add(i)
        assert s.contains(i)
    for i in range(ONE<<16):
        s = s.remove(i)
        assert not s.contains(i)

def test_set32():
    cdef u64 i
    cdef UintSet s = U32ArraySet3()
    for i in range(ONE<<32):
        s = s.add(i)
        assert s.contains(i)
    for i in range(ONE<<32):
        s = s.remove(i)
        assert not s.contains(i)

